package Graph.Medium;

import java.util.LinkedList;
import java.util.Queue;

public class LC0994 {
    public int orangesRotting(int[][] grid) {
        if (grid == null) return -1;
        int[][] deltas = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Queue<int[]> queue = new LinkedList<>();
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int thisLevelCount = 0, nextLevelCount = 0;
        boolean hasOranges = false, hasRottenOranges = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int value = grid[i][j];
                if (value != 0) hasOranges = true;
                if (value == 2) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                    thisLevelCount++;
                    hasRottenOranges = true;
                }
            }
        }
        if (!hasOranges) return 0;
        if (!hasRottenOranges) return -1;

        int nMinutes = 0;
        // 广度优先遍历
        while (!queue.isEmpty()) {
            int[] coordinate = queue.poll();
            int i = coordinate[0], j = coordinate[1];
            // 遍历周围网格
            for (int[] delta : deltas) {
                int newI = i + delta[0], newJ = j + delta[1];
                if (newI < 0 || newI >= m || newJ < 0 || newJ >= n) continue;
                if (visited[newI][newJ] || grid[newI][newJ] != 1) continue;
                // 没有访问过且是新鲜橘子
                queue.offer(new int[]{newI, newJ});
                visited[newI][newJ] = true;
                grid[newI][newJ] = 2;
                nextLevelCount++;
            }

            thisLevelCount--;
            if (thisLevelCount <= 0) {
                if (nextLevelCount > 0) nMinutes++; // 还有下一层
                thisLevelCount = nextLevelCount;
                nextLevelCount = 0;
            }
        }

        // 检查是否所有橘子都已腐烂
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) return -1;
            }
        }

        return nMinutes;
    }
}
